home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / ddj0190.arc / STEVENS.LST < prev    next >
File List  |  1989-12-19  |  6KB  |  254 lines

  1. _C PROGRAMMING COLUMN_
  2. by Al Stevens
  3.  
  4. [LISTING ONE]
  5.  
  6. /* ----------- textsrch.h ---------- */
  7.  
  8. #define OK    0
  9. #define ERROR !OK
  10.  
  11. #define MXTOKS 25           /* maximum number of tokens */
  12. #define MAXFILES 512        /* maximum number of files  */
  13. #define MAPSIZE MAXFILES/16 /* number of ints/map       */
  14.  
  15. /* ---- the search decision bitmap (one bit per file) ---- */
  16. struct bitmap {
  17.     int map[MAPSIZE];
  18. };
  19.  
  20. /* ------- the postfix expression structure -------- */
  21. struct postfix  {
  22.     char pfix;      /* tokens in postfix notation */
  23.     char *pfixop;   /* operand strings            */
  24. };
  25.  
  26. /* --------- the postfix stack ---------- */
  27. extern struct postfix pftokens[];
  28. extern int xp_offset;
  29.  
  30. /* --------- expression token values ---------- */
  31. #define TERM     0
  32. #define OPERAND 'O'
  33. #define AND     '&'
  34. #define OR      '|'
  35. #define OPEN    '('
  36. #define CLOSE   ')'
  37. #define NOT     '!'
  38. #define QUOTE   '"'
  39.  
  40. /* ---------- textsrch prototypes ---------- */
  41. struct postfix *lexical_scan(char *expr);
  42. struct bitmap exinterp(void);
  43. void init_database(void);
  44. struct bitmap search(char *word);
  45. void process_result(struct bitmap);
  46.  
  47.  
  48. [LISTING TWO]
  49.  
  50. /* ------------ exinterp.c --------------- */
  51.  
  52. /*
  53.  * An expression interpreter that processes the
  54.  * tokens on a postfix stack.
  55.  */
  56.  
  57. #include "textsrch.h"
  58.  
  59. static struct postfix *pf = pftokens;
  60.  
  61. static struct bitmap pop(void);
  62. static struct bitmap not(struct bitmap map1);
  63. static struct bitmap and(struct bitmap map1, struct bitmap map2);
  64. static struct bitmap or(struct bitmap map1, struct bitmap map2);
  65.  
  66. /* ----- entry to the interpreter
  67.          returns a bitmap which indicates the files
  68.          that match a search expression ------------- */
  69. struct bitmap exinterp(void)
  70. {
  71.     /* ------- find the top of the postfix stack ------- */
  72.     while (pf->pfix != TERM)
  73.         pf++;
  74.     /* ------- get the result of the expression ------- */
  75.     return pop();
  76. }
  77.  
  78. /* ------ pops an operand and converts it to a bit map ------ */
  79. static struct bitmap pop(void)
  80. {
  81.     struct bitmap map1;
  82.     switch ((--pf)->pfix)   {
  83.         case OPERAND:
  84.             map1 = search(pf->pfixop);
  85.             break;
  86.         case NOT:
  87.             map1 = not(pop());
  88.             break;
  89.         case AND:
  90.             map1 = and(pop(), pop());
  91.             break;
  92.         case OR:
  93.             map1 = or(pop(), pop());
  94.             break;
  95.         default:
  96.             break;
  97.     }
  98.     return map1;
  99. }
  100.  
  101. /* ------- unary <not> operator ----------- */
  102. static struct bitmap not(struct bitmap map1)
  103. {
  104.     int i;
  105.     for (i = 0; i < MAPSIZE; i++)
  106.         map1.map[i] = ~map1.map[i];
  107.     return map1;
  108. }
  109.  
  110. /* ------- binary <and> operator -------------- */
  111. static struct bitmap and(struct bitmap map1, struct bitmap map2)
  112. {
  113.     int i;
  114.     for (i = 0; i < MAPSIZE; i++)
  115.         map1.map[i] &= map2.map[i];
  116.     return map1;
  117. }
  118.  
  119. /* ------- binary <or> operator -------------- */
  120. static struct bitmap or(struct bitmap map1, struct bitmap map2)
  121. {
  122.     int i;
  123.     for (i = 0; i < MAPSIZE; i++)
  124.         map1.map[i] |= map2.map[i];
  125.     return map1;
  126. }
  127.  
  128.  
  129. [LISTING THREE]
  130.  
  131. /* ---------- search.c ----------- */
  132.  
  133. /*
  134.  * stub functions to simulate the TEXTSRCH retrieval process
  135.  */
  136.  
  137. #include <stdio.h>
  138. #include <dir.h>
  139. #include <string.h>
  140. #include <process.h>
  141. #include "textsrch.h"
  142.  
  143. static char names[MAXFILES][13];
  144. static int namect;
  145. static void setbit(struct bitmap *map1, int bit);
  146. static int getbit(struct bitmap *map1, int bit);
  147.  
  148. /* --------- initialize the data base environment --------- */
  149. void init_database(void)
  150. {
  151.     struct ffblk ff;
  152.     int rtn;
  153.     rtn = findfirst("*.txt", &ff, 0);
  154.     while (rtn != -1 && namect < MAXFILES)  {
  155.         strcpy(names[namect++], ff.ff_name);
  156.         rtn = findnext(&ff);
  157.     }
  158. }
  159.  
  160. /* ------ search the data base for a match on a word ------ */
  161. struct bitmap search(char *word)
  162. {
  163.     int i;
  164.     FILE *fp;
  165.     char str[80];
  166.     struct bitmap map1;
  167.  
  168.     for (i = 0; i < MAPSIZE; i++)
  169.         map1.map[i] = 0;
  170.     sprintf(str, "grep -l -i %s *.txt >hits", word);
  171.     system(str);
  172.     if ((fp = fopen("hits", "rt")) != NULL) {
  173.         while (fgets(str, 80, fp) != NULL)  {
  174.             *strchr(str, ':') = '\0';
  175.             for (i = 0; i < MAXFILES; i ++) {
  176.                 if (stricmp(str+5, names[i]) == 0)  {
  177.                     setbit(&map1, i);
  178.                     break;
  179.                 }
  180.             }
  181.         }
  182.         fclose(fp);
  183.     }
  184.     return map1;
  185. }
  186.  
  187. /* ---- process the result of a query expression search ---- */
  188. void process_result(struct bitmap map1)
  189. {
  190.     int i;
  191.     for (i = 0; i < MAXFILES; i++)
  192.         if (getbit(&map1, i))
  193.             printf("\n%s", names[i]);
  194. }
  195.  
  196. /* ------ sets a designated bit in the bit map ------ */
  197. static void setbit(struct bitmap *map1, int bit)
  198. {
  199.     int off = bit / 16;
  200.     int mask = 1 << (bit % 16);
  201.     map1->map[off] |= mask;
  202. }
  203.  
  204. /* ------ tests a designated bit in the bit map ------ */
  205. static int getbit(struct bitmap *map1, int bit)
  206. {
  207.     int off = bit / 16;
  208.     int mask = 1 << (bit % 16);
  209.     return map1->map[off] & mask;
  210. }
  211.  
  212.  
  213. [LISTING FOUR]
  214.  
  215.  
  216. /* ----------- textsrch.c ------------- */
  217.  
  218. /*
  219.  * The TEXTSRCH program.
  220.  */
  221.  
  222. #include <stdio.h>
  223. #include <process.h>
  224. #include <string.h>
  225. #include "textsrch.h"
  226.  
  227. void main(void)
  228. {
  229.     char expr[80];
  230.     /* -------- initialize the text data base --------- */
  231.     init_database();
  232.     do  {
  233.         /* ----- read the expression from the console ------ */
  234.         printf("\nEnter the search expression:\n");
  235.         gets(expr);
  236.         if (*expr)  {
  237.             /* --- scan for errors and convert to postfix --- */
  238.             if (lexical_scan(expr) == NULL) {
  239.                 /* ---- the expression is invalid ---- */
  240.                 while(xp_offset--)
  241.                     putchar(' ');
  242.                 putchar('^');
  243.                 printf("\nSyntax Error");
  244.                 exit(1);
  245.             }
  246.             /* --- interpret the expression, search the data base,
  247.                 and process the hits ------- */
  248.             process_result(exinterp());
  249.         }
  250.     } while (*expr);
  251. }
  252.  
  253.  
  254.